// 遍历二叉树并返回特定路径

function findPathRecursive(root, target){
    if(!root) return [];

    function dfs(node, path){
        if(!node) return null;
        path.push(node.val);

        if(node.val === target){
            return [...path];
        }

        const left = dfs(node.left, path);
        if(left) return left;  // 如果左子树找到路径，直接返回

        const right = dfs(node.right, path);
        if(right) return right;  // 如果右子树找到路径，直接返回

        path.pop();  // 回溯
        return null;  // 没有找到路径
    }

    const result = dfs(root, []);
    return result || [];  // 如果没有找到，返回空数组
}

// 定义二叉树节点结构
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// 测试用例1: 基本功能测试 - 找到目标节点路径
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);
root1.left.right = new TreeNode(5);

console.log("测试1 - 查找存在的节点:");
console.log(findPathRecursive(root1, 5)); // 应该输出 [1, 2, 5]

// 测试用例2: 查找根节点
console.log("测试2 - 查找根节点:");
console.log(findPathRecursive(root1, 1)); // 应该输出 [1]

// 测试用例3: 目标节点不存在
console.log("测试3 - 查找不存在的节点:");
console.log(findPathRecursive(root1, 6)); // 应该输出 undefined

// 测试用例4: 空树
console.log("测试4 - 空树:");
console.log(findPathRecursive(null, 1)); // 应该输出 []

// 测试用例5: 只有根节点的树
const root2 = new TreeNode(10);
console.log("测试5 - 单节点树(找到):");
console.log(findPathRecursive(root2, 10)); // 应该输出 [10]

console.log("测试5 - 单节点树(未找到):");
console.log(findPathRecursive(root2, 5)); // 应该输出 undefined

// 测试用例6: 复杂树结构
const root3 = new TreeNode(1);
root3.left = new TreeNode(2);
root3.right = new TreeNode(3);
root3.left.left = new TreeNode(4);
root3.left.right = new TreeNode(5);
root3.right.left = new TreeNode(6);
root3.right.right = new TreeNode(7);
root3.left.left.left = new TreeNode(8);

console.log("测试6 - 复杂树结构:");
console.log(findPathRecursive(root3, 8)); // 应该输出 [1, 2, 4, 8]

